#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

class Newton_formula
{
 private:

  vector<double> x,y;
  vector<vector<double>> f;
  int n;

 public:

 Newton_formula(vector<double> &x1, vector<double> &y1) : x(x1), y(y1)
  {
    n = x.size();
    f.resize(n);
    for(int i = 0; i < n; i++)
      {
	f[i].resize(n);
	f[i][0] = y[i];
      }
    for(int i = 1; i < n; i++)
      {  
	for(int j = i; j < n; j++)
	  f[j][i] = (f[j][i-1] - f[j-1][i-1])/(x[j] - x[j-i]);
      }
  };

  double operate(double input)
  {
    double res = 0;
    for(int i = 0; i < n; i++)
      {
	double temp = f[i][i];
	for(int j = 0; j < i; j++)
	  temp *= input - x[j];
	res += temp;
      }
    return res;
  }
};

class Hermite_formula
{
  private:

  vector<double> x,y,dy;
  vector<vector<double>> f;
  int n;

 public:

 Hermite_formula(vector<double> &x1, vector<double> &y1, vector<double> &dy1) : x(x1), y(y1), dy(dy1)
  {
    n = x.size();
    f.resize(n);
    for(int i = 0; i < n; i++)
      {
	f[i].resize(n);
	f[i][0] = y[i/2];
      }
    for(int i = 1; i < n; i++)
      {
	if(x[i] == x[i-1])
	  f[i][1] = dy[i/2];
	else
	  f[i][1] = (f[i][0] - f[i-1][0])/(x[i] - x[i-1]);
      }
    for(int i = 2; i < n; i++)
      {  
	for(int j = i; j < n; j++)
	  f[j][i] = (f[j][i-1] - f[j-1][i-1])/(x[j] - x[j-i]);
      }
  };

  double operate(double input)
  {
    double res = 0.0;
    for(int i = 0; i < n; i++)
      {
	double temp = f[i][i];
	for(int j = 0; j < i; j++)
	  temp *= input - x[j];
	res += temp;
      }
    return res;
  }
};

